import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

public class demo2 {
    public static String replaceWords(List<String> dictionary, String sentence) {
        HashSet<String> map = new HashSet<>();
        for (String t:
             dictionary) {
            map.add(t);
        }
        int slow=0;
        int fast=1;
        StringBuilder ret = new StringBuilder();
        while(fast<sentence.length()) {
            String tem = sentence.substring(slow,fast);
            if(map.contains(tem)) {
                ret.append(tem);
                ret.append(' ');
                while(sentence.charAt(fast)!=' ') {
                    fast++;
                }
                fast++;
                slow=fast;
            } else {
                fast++;
                if(sentence.charAt(fast)==' ') {
                    ret.append(sentence.substring(slow,fast));
                    ret.append(' ');
                    fast++;
                    slow=fast;
                }
            }
        }
        return ret.toString();
    }

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("cat");
        list.add("bat");
        list.add("rat");
        replaceWords(list,"the cattle was rattled by the battery");
    }
}
